The present invention relates to a Viterbi decoder provided in a receiver for decoding an error-correcting encoded information symbol string in a communication system in which an information symbol string is transmitted after being error-correcting encoded by means of a feedback-type convolutional encoder and quadrature amplitude-modulated.
In the digital communication field, error-correcting encoding methods and modulation methods have conventionally been considered as separate and independent subjects. Recently however, an encoded modulation technique that combines error-correcting techniques and modulation/demodulation techniques has been proposed (G. Ungerboeck, Channel Coding with Multilevel/Phase Signals, IEEE Transactions on Information Theory, vol. IT-28, January 1983). This proposed encoded modulation technique is, formally speaking, a technique of quadrature amplitude modulation of an error-correcting encoded information symbol string which is generated by error-correcting encoding an information symbol string by means of a convolutional encoder, but in the process of quadrature amplitude modulation, a measure has been taken for the arrangement of transmission symbol points. According to this measure, in the convolutional encoder, through the addition of 1-bit redundancy based on the state of finite state memories provided in the convolutional encoder, an N-bit information string is converted to an (N+1)-bit error-correcting encoded information symbol string. The error-correcting encoded information symbol string, when quadrature amplitude-modulated, is mapped onto one of 2.sup.N+1 transmission symbol points. The 2.sup.N+1 transmission symbol points are then arranged in a two-dimensional plane based on an I-axis and a Q-axis. The error-correcting encoded information symbol string is mapped onto one of the two-dimensionally distributed 2.sup.N+1 transmission symbol points in accordance with its value. As described in the above-mentioned reference, the 2.sup.N+1 transmission symbol points are divided into subsets each of which is constituted from two transmission symbol points. The Euclidean distance between the two transmission symbol points belonging to each subset is then made greater than the Euclidean distance between two arbitrary transmission symbol points. This manner of distribution of each transmission symbol point can be realized by employing the state transition of the finite state memories provided in the convolutional encoder and selecting subsets belonging to the distributed transmission symbol points in order to make available only a few series in accordance with the state transition. Consequently, in this encoded modulation technique, the process up to prescribing the two-dimensional arrangement of the transmission symbol points can be accomplished as the error-correcting encoding process.
FIG. 1 shows the construction of one example of a feedback-type convolutional encoder 40 which can obtain 4-bit error-correcting encoded information symbol string (y.sub.3 y.sub.2 y.sub.1 y.sub.0) through the addition of one redundant bit (y.sub.0) to 3-bit information symbol string (x.sub.3 x.sub.2 x.sub.1). The 3-bit information symbol string (x.sub.3 x.sub.2 x.sub.1) and 4-bit error-correcting encoded information symbol string (y.sub.3 y.sub.2 y.sub.1 y.sub.0) have the relation x.sub.3 =y.sub.3, x.sub.2 =y.sub.2, and x.sub.1 =y.sub.1. Each of two lower-order bits x.sub.2, x.sub.1 of 3-bit information symbol string (x.sub.3 x.sub.2 x.sub.1) is an encoding bit having influence on the state transition of the feedback-type convolutional encoder 40. The highest-order bit x.sub.3 of the 3-bit information symbol string (x.sub.3 x.sub.2 x.sub.1) is a noncoding bit having no influence on the state transition of the feedback-type convolutional encoder 40.
The feedback-type convolutional encoder 40 includes a first register 41.sub.1, a second register 41.sub.2, a third register 41.sub.3, a first exclusive OR circuit 42.sub.1, and a second exclusive OR circuit 42.sub.2. The first to third registers 41.sub.1 -41.sub.3 and the first and second exclusive OR circuits 42.sub.1, 42.sub.2 are connected together in a series in the following order: the first register 41.sub.1, the first exclusive OR circuit 42.sub.1, the second register 41.sub.2, the second exclusive OR circuit 42.sub.2, and the third register 41.sub.3. The output signal of the third register 41.sub.3 is fed back to the first register 41.sub.1. The first exclusive OR circuit 42.sub.1 is provided for finding the exclusive logical sum of the output signal of the first register 41.sub.1 and encoding bit x.sub.1, that is, the lowest-order bit of 3-bit information symbol string (x.sub.3 x.sub.2 x.sub.1). The second exclusive 0R circuit 42.sub.2 is provided for finding the exclusive logical sum of the output signal of the second register 41.sub.2 and encoding bit x.sub.2, that, is the second low-order bit of 3-bit information symbol string (x.sub.3 x.sub.2 x.sub.1). As shown in FIG. 1, the feedback-type convolutional encoder 40 has eight states S.sub.0 -S.sub.8 corresponding to values i.sub.0 -i.sub.2 of the first through third registers 41.sub.1 -41.sub.3. In addition, the feedback-type convolutional encoder 40 has an encoding rate of "2/3."
As shown in FIG. 2, 4-bit error-correcting encoded information symbol string (y.sub.3 y.sub.2 y.sub.1 y.sub.0) outputted from the feedback-type convolutional encoder 40 is quadrature amplitude-modulated by being mapped onto one of 16 transmission symbol points a-h, a'-h' distributed two-dimensionally on the I-axis-Q-axis plane in accordance with its value. Here, 4-bit error-correcting encoded information symbol string (0000) is mapped onto transmission symbol point a, and 4-bit error-correcting encoded information symbol string (0001) is mapped onto transmission symbol point b. Four-bit error-correcting encoded information symbol string (0010) is mapped onto transmission symbol point c, and 4-bit error-correcting encoded information symbol string (0011) is mapped onto transmission symbol point d. Four-bit error-correcting encoded information symbol string (0100) is mapped onto transmission symbol point e, and 4-bit error-correcting encoded information symbol string (0101) is mapped onto transmission symbol point f. Four-bit error-correcting encoded information symbol string (0110) is mapped onto transmission symbol point g, and 4-bit error-correcting encoded information symbol string (0111) is mapped onto transmission symbol point h. Four-bit error-correcting encoded information symbol string (1000) is mapped onto transmission symbol point a', and 4-bit error-correcting encoded information symbol string (1001) is mapped onto transmission symbol point b'. Four-bit error-correcting encoded information symbol string (1010) is mapped onto transmission symbol point c', and 4-bit error-correcting encoded information symbol string (1011) is mapped onto transmission symbol point d'. Four-bit error-correcting encoded information symbol string (1100) is mapped onto transmission symbol point e', and 4-bit error-correcting encoded information symbol string (1101) is mapped onto transmission symbol point f'. Four-bit error-correcting encoded information symbol string (1110) is mapped onto transmission symbol point g', and 4-bit error-correcting encoded information symbol string (1111) is mapped onto transmission symbol point h'. In addition, the previously mentioned subsets are, in this case, eight subsets A-H where subset A={a, a'}, subset B={b, b'}, subset C={c, c'}, subset D={d, d'}, subset E={e, e'}, subset F={f, f'}, subset G={g, g'}, and subset H={h, h'}.
As described in the above reference, the decoding of an information symbol string that has been error-correcting encoded as well as quadrature amplitude-modulated as described above can be carried out through the use of the Viterbi algorithm known as the maximum likelihood decoding method. The above-mentioned reference, however, does not touch on the concrete construction of a Viterbi decoder. The inventors investigated the above-described decoding of an error-correcting encoded information symbol string using a Viterbi decoder 20 of typical construction as shown in FIG. 3.
The Viterbi decoder 20 includes a branch metric generator 23, a subset maximum likelihood estimator 24, an accumulator switch circuit (hereinafter referred to as ACS circuit 25), a most likely path setter 27, a noncoding bit detector 29, a selector 28 and a path-memory circuit 86. A transmitted signal sent from a transmitter to a receiver is converted to two demodulated signals by being orthogonal-synchronousdetected in an orthogonal synchronous detector (not shown). The amplitudes of the two demodulated signals are each quantized by a quantization circuit (not shown), and the two demodulated signals are thereby converted to m-bit I-channel data Ich and m-bit Q-channel data Qch. I-channel data Ich and Q-channel data Qch are both 2m-value soft decision data. I-channel data Ich and Q-channel data Qch are inputted to the branch metric generator 23 and the noncoding bit detector 29 by way of two input terminals 21, 22, respectively.
The distances (branch metrics) between a reception symbol point and each transmission symbol point (corresponding to each transmission symbol point a-h, a'-h'shown in FIG. 2) are each found in the branch metric generator 23. For example, if the reception symbol point on a plane made up of an I-axis and a Q-axis for the two demodulated signals obtained by orthogonal-synchronous-detection of the transmitted signal is located at reception symbol point R shown in FIG. 4 because of the addition of noise in the transmission path, branch metrics BM0.sub.0 -BM7.sub.0 and BM0.sub.1 -BM7.sub.1 are each found for reception symbol point R in the branch metric generator 23 as shown below:
Branch metric BM0.sub.0 =the distance from reception symbol point R to transmission symbol point a PA0 Branch metric BM0.sub.1 =the distance from reception symbol point R to transmission symbol point a' PA0 Branch metric BM1.sub.0 =the distance from reception symbol point R to transmission symbol point b PA0 Branch metric BM1.sub.1 =the distance from reception symbol point R to transmission symbol point b' PA0 Branch metric BM2.sub.0 =the distance from reception symbol point R to transmission symbol point c PA0 Branch metric BM2.sub.1 =the distance from reception symbol point R to transmission symbol point c' Branch metric BM3.sub.0 =the distance from reception symbol point R to transmission symbol point d PA0 Branch metric BM3.sub.1 =the distance from reception symbol point R to transmission symbol point d' PA0 Branch metric BM4.sub.0 =the distance from reception symbol point R to transmission symbol point e PA0 Branch metric BM4.sub.1 =the distance from reception symbol point R to transmission symbol point e' PA0 Branch metric BM5.sub.0 =the distance from reception symbol point R to transmission symbol point f PA0 Branch metric BM5.sub.1 =the distance from reception symbol point R to transmission symbol point f' PA0 Branch metric BM6.sub.0 =the distance from reception symbol point R to transmission symbol point g PA0 Branch metric BM6.sub.1 =the distance from reception symbol point R to transmission symbol point g' PA0 Branch metric BM7.sub.0 =the distance from reception symbol point R to transmission symbol point h PA0 Branch metric BM7.sub.1 =the distance from reception symbol point R to transmission symbol point h'
The branch metrics are proportional to Euclidean distances and have proportionally smaller values as the Euclidean distances increase.
In the subset maximum likelihood estimator 24, branch metrics BM0.sub.0 -BM7.sub.0, BM0.sub.1 -BM7.sub.1 sent thereto from the branch metric generator 23 are divided between eight subsets A'-H', where subset A'={BM0.sub.0, BM0.sub.1 }, subset B'={BM1.sub.0, BM1.sub.1 56 , subset C'={BM2.sub.0, BM2.sub.1 }, subset D'={BM3.sub.0, BM3.sub.1 }, subset E' ={BM4.sub.0, BM4.sub.1 }, subset F'={BM5.sub.0, BM5.sub.1 }, subset G'={BM6.sub.0, BM6.sub.1 }, and subset H'={BM7.sub.0, BM7.sub.1 }, following which branch metric representative values BM0-BM7 in each subset are determined by selecting the branch metric with the larger value in each subset A'-H'. Branch metric representative values BM0-BM7 for each selected branch metric are outputted from the subset maximum likelihood estimator 24 to the ACS circuit 25. In addition, information indicating which branch metric was selected in each subset A'-H'is outputted from the subset maximum likelihood estimator 24 to the noncoding bit detector 29.
In the noncoding bit detector 29, based on the information sent thereto from the subset maximum likelihood estimator 24 and using I-channel data Ich and Q-channel data Qch, the noncoding bits of the transmission symbol points relating to branch metric representative values BM0-BM7 are extracted. At this point, the noncoding bit of 4-bit error-correcting encoded information symbol string (y.sub.3 y.sub.2 y.sub.1 y.sub.0) is y.sub.3, but each of the noncoding bits extracted in the noncoding bit detector 29 is represented by y.sub.3.sup.i. In other words, extracted noncoding bit y.sub.3.sup.i represents the representative value of the noncoding bit of subset i when subset i={A, B, C, D, E, F, G, H}.
fin the ACS circuit 25, in accordance with each branch metric representative value BM0-BM7 sent thereto from the subset maximum likelihood estimator 24 and all of the state transitions prescribed by the feedback-type convolutional encoder 40 shown in FIG. 1, each of the path metric accumulated values which are held by the several states combined in transition with one of eight states S.sub.0 -S.sub.7 is added to the predetermined representative value of branch metric representative values BM0-BM7, and the greatest addition value becomes the new path metric accumulated value for the one state. In this way, new path metric accumulated values PM0-PM7 for states S.sub.0 -S.sub.7 are obtained. In addition, from the information of the path selected for every state S.sub.0 -S.sub.7 at this time, eight selector signals SEL.sub.0 -SEL.sub.7, each of which corresponding to a respective state S.sub.0 -S.sub.7, are formed. As shown in FIG. 5, the actual components of the circuit in the ACS circuit 25 for finding path metric accumulated value PM0 and select signal SEL.sub.0 for state S.sub.0 include first to fourth path metric holding circuits 51.sub.1 -51.sub.4, first to fourth adders 52.sub.1 -52.sub.4, a comparator 53, and a selector 54. Path metric accumulated value PM0 for state S.sub.0 is held in the first path metric holding circuit 51.sub.1. Path metric accumulated value PM2 for state S.sub.2 is held in the second path metric holding circuit 51.sub.2. Path metric accumulated value PM4 for state S.sub.4 is held in the third path metric holding circuit 51.sub.3. Path metric accumulated value PM6 for state S.sub.6 is held in the fourth path metric holding circuit 51.sub.4. In the first adder 52.sub.1, branch metric representative value BM0 sent thereto from the subset maximum likelihood estimator 24 is added to path metric accumulated value PM0 sent thereto from the first path metric holding circuit 51.sub.1. In the second adder 52.sub.2, branch metric representative value BM4 sent thereto from the subset maximum likelihood estimator 24 is added to path metric accumulated value PM2 sent thereto from the second path metric holding circuit 51.sub.2. In the third adder 52.sub.3, branch metric representative value BM2 sent thereto from the subset maximum likelihood estimator 24 is added to the path metric accumulated value PM4 sent thereto from the third path metric holding circuit 51.sub.3. In the fourth adder 52.sub.4, the branch metric representative value BM6 sent thereto from the subset maximum likelihood estimator 24 is added to the path metric accumulated value PM6 sent thereto from the fourth path metric holding circuit 51.sub.4. In the comparator 53, the output signals of the first to fourth adders 52.sub.1 -52.sub.4 are compared and select signal SEL.sub.0 is generated indicating the adder corresponding to the greatest output signal. In the selector 54, one of the output signals of the first to fourth adders 52.sub.1 -52.sub.4 is selected in accordance with select signal SEL.sub.0 sent thereto from the comparator 53 and then sent to the first path metric holding circuit 51.sub.1 and held in the first path metric holding circuit 51.sub.1.
Path metric accumulated values PM1-PM7 and select signals SEL.sub.1 -SEL.sub.7 for other states S.sub.1 -S.sub.7 are at the same time found in the same manner as path metric accumulated value PM0 and select signal SEL.sub.0 for state S.sub.0. The combinations of the path metric accumulated value and the branch metric representative value inputted to each of the adders corresponding to the first to fourth adders 52.sub.1 -52.sub.4 shown in FIG. 5 are shown in Table 1.
TABLE 1 __________________________________________________________________________ COMBINATION STATE FIRST ADDER SECOND ADDER THIRD ADDER FOURTH ADDER __________________________________________________________________________ S.sub.1 PM0 and BM4 PM2 and BM0 PM4 and BM6 PM6 and BM2 S.sub.2 PM0 and BM2 PM2 and BM6 PM4 and BM0 PM6 and BM4 S.sub.3 PM0 and BM6 PM2 and BM2 PM4 and BM4 PM6 and BM0 S.sub.4 PM1 and BM1 PM3 and BM5 PM5 and BM3 PM7 and BM7 S.sub.5 PM1 and BM5 PM3 and BM1 PM5 and BM7 PM7 and BM3 S.sub.6 PM1 and BM3 PM3 and BM7 PM5 and BM1 PM7 and BM5 S.sub.7 PM1 and BM7 PM3 and BM3 PM5 and BM5 PM7 and BM1 __________________________________________________________________________
Each select signal SEL.sub.0 -SEL.sub.7 is outputted from the ACS circuit 25 to the path-memory circuit 86.
As shown in FIG. 3, the path-memory circuit 86 includes a first memory P1 for finding an estimated value (represented as y.sub.1) of second lower-order encoding bit y.sub.1 of 4-bit error-correcting encoded information symbol string (y.sub.3 y.sub.2 y.sub.1 y.sub.0), a second memory P2 for finding an estimated value (represented as y.sub.2) of second higher-order encoding bit y.sub.2, and a third memory P3 for finding an estimated value (represented as y.sub.3) of highest-order encoding bit y.sub.3. In addition, each of the first to third memories P1-P3 has the same construction, in concrete terms, as the j-level construction shown in FIG. 6. Here, each level is made up of eight selectors 91.sub.0 -91.sub. 7 for selecting one of the four input signals in accordance with selector signals SEL.sub.0 -SEL.sub.7 sent thereto from the ACS circuit 25 and eight registers 92.sub.0 -92.sub.7 for storing the output signals of the selectors 91.sub.0 -91.sub.7. As shown in FIG. 6, the input signal of each selector 91.sub.0 -91.sub.7 on the first level is, in the first memory P1, an initial value (0011) for selector 91.sub.0 of state S.sub.0, selector 91.sub.1 of state S.sub.1, selector 91.sub.4 of state S.sub.4, and selector 91.sub.5 of state S.sub.5 and an initial value (1100) for the remaining selectors 91.sub.2, 91.sub.3, 916, and 917. In the second memory P2, it is an initial value (0101) for selector 91.sub.0 of state S.sub. 0, selector 91.sub.2 of state S.sub.2, selector 91.sub.4 of state S.sub.4, and selector 91.sub.6 of state S.sub.6 and an initial value (1010) for the remaining selectors 91.sub.1, 91.sub.3, 91.sub.5, and 91.sub.7. In the third memory P3, the signal inputted to each of the selectors 91.sub.0 -91.sub.7 of states S.sub.0 -S.sub.7 is the respective noncoding bit of noncoding bits y.sub.3.sup.A -y.sub.3.sup.H sent thereto from the noncoding bit detector 29. The input signals for each selector 91.sub.0 -91.sub.7 on the second to j-th levels are, for selectors 91.sub.0 -91.sub.3, the output signals of registers 92.sub.0, 92.sub.2, 92.sub.4, and 92.sub.6 on the preceding level, and for selectors 91.sub.4 -91.sub.7, the output signals of registers 92.sub.1, 92.sub.3, 92.sub.5, and 92.sub.7 on the preceding level. The output signal of each register 92.sub.0 -92.sub.7 on the j th level is, in the first memory P1, each respective state D0.sub.1 -D7.sub.1, in the second memory P2, each respective state D0.sub.2 -D7.sub.2, and in the third memory P3, each respective state D0.sub.3 -D7.sub.3. The operation of each selector 91.sub.0 -91.sub.7 and each register 92.sub.0 -92.sub.7 on each level is performed both simultaneously and in parallel within the time (hereinafter referred to as "symbol time") during which one 4-bit error-correcting encoded information symbol string (y.sub.3 y.sub.2 y.sub.1 y.sub.0) is sent.
In the most likely path setter 27, the sizes of path metric accumulated values PM.sub.0 -PM.sub.7 for states S.sub.0 -S.sub.7 sent thereto from the ACS circuit 25 are compared for every symbol time, and the greatest value is outputted from the most likely path setter 27 to selector 28. In selector 28, based on the output signal of the most likely path setter 27, one combination is chosen among states D0.sub.1 -D7.sub.1, D0.sub.2 -D7.sub.2, D0.sub.3 -D7.sub.3 (hereinafter referred to as "D0-D7") for each memory P1-P3 sent thereto from the path-memory circuit 86. In other words, in a case where the output signal of the most likely path setter 27 indicates path metric accumulated value PM0 of state S.sub.0, state D0.sub.1 of the first memory P1, state D0.sub.2 of the second memory P2, and state D0.sub.3 of the third memory P3 are selected. The values of the states selected in selector 28 are estimated values (y.sub.3 y.sub.2 y.sub.1) of the three higher-order bits (y.sub. 3 y.sub.2 y.sub.1) of 4-bit error-correcting encoded information symbol string (y.sub.4 y.sub.3 y.sub.2 y.sub.1) and are taken as desired decoded data (x.sub.3 x.sub.2 x.sub.1).
The above operation is repeated every time I-channel data Ich and Q-channel data Qch are inputted to the input terminals 21, 22 respectively, and decoded data (x.sub.3 x.sub.2 x.sub.1) is obtained after j symbol times after the inputting of I-channel data Ich and Q-channel data Qch to the input terminals 21, 22.
However, because the Viterbi decoder 20 of typical construction shown in FIG. 3 is of a construction for estimating the noncoding bit in the path-memory circuit 86, the following problem is encountered. When using only the feed-back-type convolutional encoder 40 shown in FIG. 1, in cases where the number of bits of information symbol strings is increased for transmitting a large volume of information, the number of noncoding bits increases to the same extent as the increased bits, and as a result, it is necessary to increase to an equal extent the number of memories provided in the path-memory circuit 86. In other words, the scale of the circuits of the path-memory circuit 86 increases in accordance with the number of noncoding bits, thereby..raising problems regarding the cost and potential for large-scale integrated circuit (LSI).